#pragma once
#include<iostream>
#include<fstream>
#include<vector>
#include<map>
#include"negative_array.h"
#include<string>
using namespace std;

void Reading_Files(const vector<string>& first_file,const vector<string>& second_file, vector<int>& first_string, vector<int>& second_string, map<int, string>& int_to_string)
{
	int first_length = first_file.size();
	int second_length = second_file.size();
	map<string, int> bijection;
	int hash = 0;
	string s;
	for(int letter = 0; letter < first_length; ++letter)
	{
		s = first_file[letter];
		if (!bijection[s])
		{
			++hash;
			bijection[s] = hash;
			int_to_string[hash] = s;
		}
		first_string.push_back(bijection[s]);
	}

	for(int letter = 0; letter < second_length; ++letter)
	
	{
		s = second_file[letter];
		if (!bijection[s])
		{
			++hash;
			bijection[s] = hash;
			int_to_string[hash] = s;
		}
		second_string.push_back(bijection[s]);
	}
}

bool IsGoodEq(const vector<int>& first_string, const vector<int>& second_string, int coord_x, int coord_y)
{
	return (coord_x >= 1 && coord_y >= 1 && coord_x <= first_string.size() && coord_y <= second_string.size() && first_string[coord_x - 1] == second_string[coord_y - 1]);
}

bool IsGoodRevEq(const vector<int>& first_string, const vector<int>& second_string, int coord_x, int coord_y)
{
	return (coord_x >= 0 && coord_y >= 0 && coord_x <= first_string.size() - 1 && coord_y <= second_string.size() - 1 && first_string[coord_x] == second_string[coord_y]);
}

int Count_Mistakes(const vector<int> &first_string, const vector<int> &second_string)
{
	int first_length = first_string.size();
	int second_length = second_string.size();
	Mapchik Furthest_Diag;
	Furthest_Diag[1] = 0;

	for(int mistakes = 0; mistakes <= first_length + second_length; ++mistakes)
	{
		for(int diagonal = - mistakes; diagonal <= mistakes; diagonal+=2)
		{
			if (diagonal == -mistakes || (diagonal < mistakes && Furthest_Diag[diagonal - 1] < Furthest_Diag[diagonal + 1]))
				Furthest_Diag[diagonal] = Furthest_Diag[diagonal + 1];
			else
				Furthest_Diag[diagonal] = Furthest_Diag[diagonal - 1] + 1;

			int coord_x = Furthest_Diag[diagonal];
			int coord_y = coord_x - diagonal;
			while (IsGoodEq(first_string, second_string, coord_x + 1, coord_y + 1))++coord_x, ++coord_y;
			Furthest_Diag[diagonal] = coord_x;
			if (coord_x == first_string.size() && coord_y == second_string.size()) return mistakes;
		}
	}
}

vector<pair<int, int> > Path_With_Zero_Mistakes(int length)
{
	vector<pair<int, int> >path;
	for(int point = 0; point <= length; ++point)path.push_back(make_pair(point, point));
	return path;
}

vector<pair<int, int> > Path_With_One_Mistake(const vector<int>& first_string, const vector<int>& second_string)
{
	int coor_X = 0;
	int coor_Y = 0;
	vector<pair<int, int> > path;
	int first_length = first_string.size();
	int second_length = second_string.size();
	path.push_back(make_pair(coor_X, coor_Y));

	while(IsGoodEq(first_string, second_string, coor_X + 1, coor_Y + 1))
		++coor_X, ++coor_Y, path.push_back(make_pair(coor_X, coor_Y));

	if (first_length > second_length)
		++coor_X; 
	else 
		++coor_Y;

		path.push_back(make_pair(coor_X, coor_Y));
		while(IsGoodEq(first_string, second_string, coor_X + 1, coor_Y + 1))
			++coor_X, ++coor_Y, path.push_back(make_pair(coor_X, coor_Y));

	return path;
}

vector<pair<int, int> > Path_With_First_Length_Zero(int second_length)
{
	vector<pair<int, int> > path;
	for(int point = 0; point <= second_length; ++point)path.push_back(make_pair(0, point));
	return path;
}

vector<pair<int, int> > Path_With_Second_Length_Zero(int first_length)
{
	vector<pair<int, int> > path;
	for(int point = 0; point <= first_length; ++point)path.push_back(make_pair(point, 0));
	return path;
}

Mapchik Make_Up_Map(const vector<int>& first_string, const vector<int>& second_string, int up_mistakes)
{
	int first_length = first_string.size();
	int second_length = second_string.size();
	Mapchik UpMap;
	UpMap[1] = 0; 
	for(int cur_mistakes = 0; cur_mistakes<= up_mistakes; ++cur_mistakes)
	{
		for(int diagonal = - cur_mistakes; diagonal <= cur_mistakes; diagonal+=2)
		{
			if (diagonal == -cur_mistakes || (diagonal < cur_mistakes && UpMap[diagonal - 1] < UpMap[diagonal + 1]))
				UpMap[diagonal] = UpMap[diagonal + 1];
				else
				UpMap[diagonal] = UpMap[diagonal - 1] + 1;

			if (UpMap[diagonal] > first_length) 
				UpMap[diagonal] = first_length;
			int coord_x = UpMap[diagonal];
			int coord_y = coord_x - diagonal;

			while (IsGoodEq(first_string, second_string, coord_x + 1, coord_y + 1))
				++coord_x, ++coord_y;

				UpMap[diagonal] = coord_x;
			}
		}
	return UpMap;
}

Mapchik Make_Down_Map(const vector<int>& first_string,const vector<int>& second_string, int down_mistakes)
{
	Mapchik DownMap;
	int first_length = first_string.size();
	int second_length = second_string.size();
	int delta = first_length - second_length;
	
	for(int cycle = delta - down_mistakes; cycle <= delta + down_mistakes; ++cycle) DownMap[cycle] = first_length;

	DownMap[delta - 1] = first_length;
	for(int cur_mistakes = 0; cur_mistakes <= down_mistakes; ++cur_mistakes)
	{
		for(int diagonal = delta + cur_mistakes; diagonal >= delta - cur_mistakes; diagonal -=2)
		{
			if (diagonal == delta + cur_mistakes || (diagonal > delta - cur_mistakes && DownMap[diagonal - 1] < DownMap[diagonal + 1]))
				DownMap[diagonal] = DownMap[diagonal - 1];
			else
				DownMap[diagonal] = DownMap[diagonal + 1] - 1;
			if (DownMap[diagonal] < 0) DownMap[diagonal] = 0;
			int coord_x = DownMap[diagonal];
			int coord_y = coord_x - diagonal;
			while (IsGoodRevEq(first_string, second_string, coord_x - 1, coord_y - 1))--coord_x, --coord_y;
			DownMap[diagonal] = coord_x;
			
		}
	}
	return DownMap;
}

vector<pair<int, int> > Finding_Way(const vector<int>& first_string, const vector<int>& second_string, int mistakes)
{
	int first_length = first_string.size();
	int second_length = second_string.size();
	int delta = first_length - second_length; 
	int up_mistakes = (mistakes + 1)/2;
	int down_mistakes = mistakes/2;

	Mapchik UpMap; 
	Mapchik DownMap; 

	vector<pair<int, int> >path;

	if (mistakes == 0)
		return Path_With_Zero_Mistakes(first_length);

	if (mistakes == 1)
		return Path_With_One_Mistake(first_string, second_string);

	if (first_length == 0)
		return Path_With_First_Length_Zero(second_length);

	if (second_length == 0)
		return Path_With_Second_Length_Zero(first_length);

	UpMap = Make_Up_Map(first_string, second_string, up_mistakes);

	DownMap = Make_Down_Map(first_string, second_string, down_mistakes);

	for(int diagonal = -up_mistakes; diagonal <= up_mistakes; diagonal += 2)
		if (diagonal >= delta - down_mistakes && diagonal <= delta + down_mistakes && UpMap[diagonal] >= DownMap[diagonal])
		{
			vector<int> first_part_first_string;
			vector<int> second_part_first_string;
			
			vector<int> first_part_second_string;
			vector<int> second_part_second_string;

			int first_point_X = DownMap[diagonal];
			int first_point_Y = DownMap[diagonal] - diagonal;

			for(int letter = 0; letter < first_point_X; ++letter) 
				first_part_first_string.push_back(first_string[letter]);
			for(int letter = 0; letter < first_point_Y; ++letter) 
				first_part_second_string.push_back(second_string[letter]);
		
			for(int letter = first_point_X; letter < first_length; ++letter) 
				second_part_first_string.push_back(first_string[letter]);
			for(int letter = first_point_Y; letter < second_length; ++letter) 
				second_part_second_string.push_back(second_string[letter]);

			vector<pair<int, int> >path1 = Finding_Way(first_part_first_string, first_part_second_string, up_mistakes); 
			vector<pair<int, int> >path2 = Finding_Way(second_part_first_string, second_part_second_string, down_mistakes);
		
            path1.pop_back();

			for(int point = 0; point < path1.size(); ++point) path.push_back(path1[point]);
			for(int point = 0; point < path2.size(); ++point) path.push_back(make_pair(path2[point].first + first_point_X, path2[point].second + first_point_Y));

			return path;
		}

}

inline
void Out(const vector<int>& first_string,const  vector<int>& second_string,const vector<pair<int, int> >& path,  map<int, string>& int_to_string)
{
	HANDLE hConsole;
	hConsole = GetStdHandle(STD_OUTPUT_HANDLE);

	int coord_x = path[0].first;
	int coord_y = path[0].second;
	for(int points = 1; points < path.size(); ++points)
		{
			int next_coord_x = path[points].first;
			int next_coord_y = path[points].second;
			if (next_coord_x - coord_x == 1 && next_coord_y - coord_y == 1){ SetConsoleTextAttribute(hConsole, 15); cout << int_to_string[first_string[coord_x]] << " ";}
			if (next_coord_x - coord_x == 0 && next_coord_y - coord_y == 1){ SetConsoleTextAttribute(hConsole, 10); cout << int_to_string[second_string[coord_y]] << " ";}
			if (next_coord_x - coord_x == 1 && next_coord_y - coord_y == 0){ SetConsoleTextAttribute(hConsole, 12); cout << int_to_string[first_string[coord_x]] << " ";}
			coord_x = next_coord_x;
			coord_y = next_coord_y;
			
		}
	cout << "\n";
}


void Compare_Two_Strings(const vector<string>& first_file,const vector<string>& second_file)
{
	vector<int> first_string;
	vector<int> second_string;
	map<int, string> int_to_string;

	Reading_Files(first_file, second_file, first_string, second_string, int_to_string); 
	int mistakes = Count_Mistakes(first_string, second_string);
	cout << "mistakes: " << mistakes << "\n";
	vector<pair<int, int> > path = Finding_Way(first_string, second_string, mistakes);
	Out(first_string, second_string, path, int_to_string);
	
	while(1){}

}